package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/12 17:24
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 */
public class Title188 {

    /**
     * 一天有k种状态：0 都不操作 、 1 第一次买、2 第一次卖、3 第二次买、4 第二次卖。。。。。
     * @param k
     * @param prices
     * @return
     */
    public static int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[] dp = new int[2 * k + 1];
        //初始化
        for (int i = 1; i < dp.length; i += 2) {
            //1 3 5
            dp[i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            //1 2 3 4 5 ..... K
            for (int j = 2; j <= 2 * k; j += 2) {
                dp[j - 1] = Math.max(dp[j - 2] - prices[i], dp[j - 1]);
                dp[j] = Math.max(dp[j - 1] + prices[i], dp[j]);
            }
        }
        return dp[2 * k];
    }


    public int maxProfit1(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[][] dp = new int[2][2 * k + 1];
        //初始化
        for (int i = 1; i < 2 * k; i += 2) {
            //1 3 5
            dp[0][i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            //1 2 3 4 5 ..... K
            for (int j = 2; j <= 2 * k; j += 2) {
                dp[i % 2][j - 1] = Math.max(dp[(i - 1) % 2][j - 2] - prices[i], dp[(i - 1) % 2][j - 1]);
                dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j - 1] + prices[i], dp[(i - 1) % 2][j]);
            }
        }
        return dp[(prices.length - 1) % 2][2 * k];
    }

    public static void main(String[] args) {
        int k = 2;
        int[] arr = {3, 2, 6, 5, 0, 3};
        maxProfit(k, arr);
    }
}
